Vehicle Routing

Next step is finding the optimal route each truck (vehicle) should take to minimize transportation cost (length of route) while making all deliveries on time.

This is essentially a constrained Travelling Salesman Problem with the constrained being on-time deliveries.

Tech Stack

I decided to go for a Solution Space approach and use Genetic Algorithm.

I have previously coded Genetic Algorithm from scratch for my course project on Travelling Salesman Problem, but used a straightforward package here:

Platypus: An optimization package offering advanced variants of Genetic Algorithm for multi-objective constrained optimization.

I used this because I indeed have multiple objectives in my problem - minimizing the distance and delivering on time.

Code Snippet

from platypus import NSGAII, Problem, Subset, nondominated

def objective(distances, vehicle_deliveries):
    def optimize(tours):
        length = 0
        for i in range(len(tours)):

            # tour_length is function for calculating length of tour
            length += tour_length(tours[i], distances)

        # constrained_time_windows is the constraint function
        return length, constraint_time_windows(tours, distances, vehicle_deliveries)
    return optimize

problem = Problem(len(vehicle_deliveries), 1, 1)
for vehicle_idx, (delivery_locations, _) in enumerate(vehicle_deliveries):
    problem.types[vehicle_idx] = Subset(list(set(delivery_locations)), len(delivery_locations))
problem.constraints[:] = "==1"
problem.function = objective(distances, vehicle_deliveries)

algorithm = NSGAII(problem, 500)
algorithm.run(10000)

solution = [s for s in nondominated(algorithm.result) if s.feasible]
if solution:
    print(solution[0].variables, solution[0].objectives)
else:
    print("No feasible solution")